package arithmetic2.day06;


import java.util.*;
import java.util.concurrent.SynchronousQueue;

/*
    二叉树
 */
public class BinaryTree {
    //二叉树的根节点
    private Node root;

    public BinaryTree(Node root) {
        this.root = root;
    }

    //先序遍历递归版
    private void preOrder(Node cur) {
        if (cur != null) {
            System.out.println(cur.value);
            preOrder(cur.leftChild);
            preOrder(cur.rightChild);
        }
    }

    public void preOrder() {
        preOrder(this.root);
    }

    /*
    先序遍历非递归版:
        每到一个节点的时候将这个节点进栈
        将这个节点出栈并打印
        将这个节点的右孩子和左孩子分别进栈
        重复上述操作
     */
    public void preOrder1() {
        //初始化一个栈
        Stack<Node> stack = new Stack<>();
        //将根节点进栈
        if (this.root != null) {
            stack.push(this.root);
            while (!stack.isEmpty()) {
                //弹出一个节点并打印
                Node node = stack.pop();
                System.out.println(node.value);
                //将这个节点的右孩子进栈
                if (node.rightChild != null) {
                    stack.push(node.rightChild);
                }
                //将这个节点的左孩子进栈
                if (node.leftChild != null) {
                    stack.push(node.leftChild);
                }
            }
        }
    }

    //中序遍历递归版
    private void inOrder(Node cur) {
        if (cur != null) {
            inOrder(cur.leftChild);
            System.out.println(cur.value);
            inOrder(cur.rightChild);
        }
    }

    public void inOrder() {
        inOrder(this.root);
    }

    /*
        中序遍历非递归版:
            对于以当前节点为根节点的树，将这个树的所有左边界依次进栈
            然后在依次弹出节点并打印，在弹出的过程中如果该节点有右孩子
            那么对于以该节点的右孩子为根的树重复上述操作
     */
    public void inOrder1() {
        if (this.root != null) {
            Stack<Node> stack = new Stack<>();
            //将整个树的所有左边界进栈
            fun(this.root, stack);
            while (!stack.isEmpty()) {
                //将这个节点的所有左边界进栈
                Node node = stack.pop();
                System.out.println(node.value);
                if (node.rightChild != null) {
                    fun(node.rightChild, stack);
                }
            }
        }
    }

    //中序遍历非递归简化版
    public void inOrder2() {
        if (this.root != null) {
            Stack<Node> stack = new Stack<>();
            Node head = this.root;
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.leftChild;
                } else {
                    Node node = stack.pop();
                    System.out.println(node.value);
                    head = node.rightChild;
                }
            }
        }
    }

    //将树的所有左边界进栈
    public void fun(Node cur, Stack<Node> stack) {
        if (cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.leftChild;
            }
        }
    }

    //后序遍历递归版
    private void postOrder(Node cur) {
        if (cur != null) {
            preOrder(cur.leftChild);
            preOrder(cur.rightChild);
            System.out.println(cur.value);
        }
    }

    public void postOrder() {
        postOrder(this.root);
    }

    /*
     后序遍历非递归版：
        将当前节点进栈
        将当前节点出栈放入到收集栈
        将当前节点的左孩子和右孩子分别进栈
        重复上述操作
        将收集栈中的节点依次弹出并打印
     */
    public void postOrder1() {
        if (this.root != null) {
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            //将根节点进栈
            stack1.push(this.root);
            while (!stack1.isEmpty()) {
                Node node = stack1.pop();
                stack2.push(node);
                if (node.leftChild != null) {
                    stack1.push(node.leftChild);
                }
                if (node.rightChild != null) {
                    stack1.push(node.rightChild);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.println(stack2.pop().value);
            }
        }
    }

    /*
      宽度优先遍历一颗二叉树:
        创建一个队列
        将一个节点放入队列
        将节点出队列并打印
        将这个节点的左子节点和右子节点分别进队列
        重复上述操作
     */
    public void breadthFist() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //删除头部元素
            Node node = queue.poll();
            System.out.println(node.value);
            if (node.leftChild != null) {
                queue.add(node.leftChild);
            }
            if (node.rightChild != null) {
                queue.add(node.rightChild);
            }
        }
    }

    /*
        求二叉树的最大宽度
     */
    public int maxWidth() {
        if (root != null) {
            //创建队列
            Queue<Node> queue = new LinkedList<>();
            //用map集合来存储节点和它的层级关系
            Map<Node, Integer> levelMap = new HashMap<>();
            //最大宽度
            int maxWidth = -1;
            //当前层次
            int curLevel = 1;
            //当前层次的节点数
            int curLevelNodes = 0;
            //将根节点加入到队列中
            queue.add(root);
            //在map集合中存储根节点的层次
            levelMap.put(root, 1);
            while (!queue.isEmpty()) {
                //将当前节点出队列
                Node node = queue.poll();
                //判断当前节点是否是换层了
                if (levelMap.get(node) == curLevel) { //没有换层
                    curLevelNodes++;
                } else {    //换层了，将上一层的宽度与当前最大宽度比较，更新最大宽度
                    maxWidth = Math.max(maxWidth, curLevelNodes);
                    //层数+1指向下一层
                    curLevel++;
                    //重置当前层次节点数量
                    curLevelNodes = 1;
                }
                //将当前节点的左子节点加入到队列中，并在map中存储层次信息
                if (node.leftChild != null) {
                    queue.add(node.leftChild);
                    levelMap.put(node.leftChild, curLevel + 1);
                }
                //将当前节点的右子节点加入到队列中，并在map中存储层次信息
                if (node.rightChild != null) {
                    queue.add(node.rightChild);
                    levelMap.put(node.rightChild, curLevel + 1);
                }
            }
            return maxWidth;
        }
        return 0;
    }

    /*
        判断二叉树是不是排序二叉树:
            这个节点的左子节点小于这个节点
            这个节点的右子节点大于等于这个节点
     */
    public boolean isBST(Node curNode) {
        if (curNode == null) {
            return true;
        }
        //判断该节点的左子树是不是BST
        boolean left = isBST(curNode.leftChild);
        if (!left) {  //当前节点的左子树不是BST
            return false;
        }
        //如果该节点左子树是一个BST，判断该节点是否小于它的左子节点或者是否大于右子节点的值
        if (curNode.leftChild != null && curNode.value <= curNode.leftChild.value) {
            return false;
        }
        if (curNode.rightChild != null && curNode.value > curNode.rightChild.value) {
            return false;
        }
        //当前节点左子树是一个BST,并且当前节点的值也大于左子节点的值小于右子节点的值,再判断当前节点的右子节点
        return isBST(curNode.rightChild);
    }

    /*
        判断一个树是否为完全二叉树:
            在宽度优先遍历的过程中如果一个节点只有右子节点没有左子节点就不是
            如果一个节点有两个节点判断下一个
            如果一个节点只有左子节点或者没有孩子节点,那么后序遍历到的所有节点必须是叶子节点
     */
    public boolean isCBT() {
        if (root == null) {
            return true;
        }
        if(root.leftChild==null && root.rightChild==null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //当前节点出队列
            Node curNode = queue.poll();
            //该节点只有右子节点
            if(curNode.rightChild!=null && curNode.leftChild!=null){
                return false;
            }
            if (curNode.leftChild!=null) {
                queue.add(curNode.leftChild);
            }
            if (curNode.rightChild!=null) {
                queue.add(curNode.rightChild);
            }
        }
        return false;
    }

    //返回树的高度
    private int height(Node node) {
        if (node != null) {
            //返回当前节点左子树和右子树的最大高度
            return Math.max(height(node.leftChild), height(node.rightChild)) + 1;
        }
        return 0;
    }

    public int height() {
        return height(this.root);
    }
}
